package com.xyhuo.leetcode.january;

/**
 * 交错字符串
 * https://leetcode.cn/problems/interleaving-string/
 *
 * @desc 一直超时，看的题解；
 * s1的前i个字符，s2的前j个字符，构成s3的前i+j个字符的充分必要条件
 *      s1[i]==s3[i+j] and s1的前i-1个元素，与s2的前j个元素构成s3的前i+j-1个元素
 *      or
 *      s2[j]==s3[i+j] and s2的前j-1个元素，与s1的前i个元素构成s3的前i+j-1个元素
 *
 * @time 2024/1/5
 */
public class IsInterleave {

//    public static void main(String[] args) {
//        IsInterleave iil = new IsInterleave();
////        boolean ans = iil.isInterleave(
////                "bcbccabcccbcbbbcbbacaaccccacbaccabaccbabccbabcaabbbccbbbaa",
////                "ccbccaaccabacaabccaaccbabcbbaacacaccaacbacbbccccbac",
////                "bccbcccabbccaccaccacbacbacbabbcbccbaaccbbaacbcbaacbacbaccaaccabcaccacaacbacbacccbbabcccccbababcaabcbbcccbbbaa");
//
//
////        boolean ans = iil.isInterleave("aabcc", "dbbca", "aadbbcbcac");
//        boolean ans = iil.isInterleave(
//                "abbb",
//                "aaba",
//                "abababbb"
//        );
//        System.out.println(ans);
//    }

    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length(), t = s3.length();

        if (n + m != t) {
            return false;
        }

        boolean[][] f = new boolean[n + 1][m + 1];

        f[0][0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    f[i][j] = f[i][j] || (f[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p));
                }
                if (j > 0) {
                    f[i][j] = f[i][j] || (f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p));
                }
            }
        }

        return f[n][m];
    }

    public boolean isInterleave1(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        search(s1.toCharArray(), 0, s2.toCharArray(), 0, s3.toCharArray(), 0);
        return ans;
    }

    private boolean ans = false;

    private void search(char[] s1, int index_1, char[] s2, int index_2, char[] s3, int index_3) {
        if (ans) {
            return;
        }
        if (index_3 >= s3.length) {
            ans = true;
            return;
        }
        if (index_1 < s1.length && s1[index_1] == s3[index_3]) {
            search(s1, index_1 + 1, s2, index_2, s3, index_3 + 1);
        }
        if (index_2 < s2.length && s2[index_2] == s3[index_3]) {
            search(s1, index_1, s2, index_2 + 1, s3, index_3 + 1);
        }
    }



    private void search1(char[] s1, int index_1, char[] s2, int index_2, char[] s3, int index_3) {
        if (ans) {
            return;
        }
        if (index_3 >= s3.length) {
            ans = true;
            return;
        }

        int s1Len = 0;
        for (int i = index_1; i < s1.length; i++) {
            if (s1[i] != s3[index_3 + s1Len] || index_3 + s1Len >= s3.length) {
                break;
            }
            s1Len++;
        }
        if (s1Len > 0) {
            for (int i = 1; i <= s1Len; i++) {
                search(s1, index_1 + i, s2, index_2, s3, index_3 + i);
            }
        }

        int s2Len = 0;
        for (int i = index_2; i < s2.length; i++) {
            if (s2[i] != s3[index_3 + s2Len] || index_3 + s2Len >= s3.length) {
                break;
            }
            s2Len++;
        }
        if (s2Len > 0) {
            for (int i = 1; i <= s2Len; i++) {
                search(s1, index_1, s2, index_2 + i, s3, index_3 + i);
            }
        }
    }
}
